package com.minglan.leetcode.java.solution2103;

/*
 * 2021年3月3日
 * 338. 比特位计数
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 * 
示例 1:
输入: 2
输出: [0,1,1]

 */
public class CountBits {

	/*
	 * 算法实现1
	 * 0-1 1-2 3-4 7-8 15-16 都是变成 1后面n个0 我们称为 highbit
	 * highbit后面的数字遵循规律，可以用 ret[i-highbit]+1获取
	 */
    public int[] countBits1(int num) {
        int[] ret = new int[num+1];
        int highbit=0;
        for(int i=1;i<=num;i++) {
            if((i&(i-1))==0) {
                highbit=i;
            }
            ret[i]=ret[i-highbit]+1;
        }
        return ret;
    }
    
    /* 
     * 算法2
     * 奇数 1 3 5 7 9 ,都是前面偶数（或者0）基础上增加一位，故直接加1
     * 0-1 10-11 110-111 1010-1011 1100-1101
     * 偶数 2-1 4-2 6-3 8-4 ,去掉最后的0，数值上是除以2，但是，bit数是不变的
     * 10-1 100-10 110-11 1000-100
     */
    public int[] countBits(int num) {
    	int [] ret = new int[num+1];
    	ret[0]=0;
    	int highbit=0;
    	for(int i=1;i<ret.length;i++ ) {
    		if((i%2)==0)
    			ret[i]=ret[i/2];
    		else
    			ret[i]=ret[i-1]+1;
    	}
    	return ret;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CountBits obj = new CountBits();
		int[] ret= obj.countBits(50);
		logarray(ret);
		
	}
	
	public static void logarray(int[] m) {
		for(int i=0;i<m.length;i++) {
			System.out.print(m[i]+" ");
		}
	}

}
